Transmission of files and streams between a sender and a recipient over a communications channel has been the subject of much literature. Preferably, a recipient desires to receive an exact copy of data transmitted over a channel by a sender with some level of certainty. Where the channel does not have perfect fidelity, which characterizes most physically realizable systems, one concern is how to deal with data that is lost or corrupted in transmission. Lost data (erasures) are often easier to deal with than corrupted data (errors) because the recipient cannot always recognize when the transmitted data has been corrupted. Many error-correcting codes have been developed to correct erasures and/or errors. Typically, the particular code used is chosen based on some information about the infidelities of the channel through which the data is being transmitted, and the nature of the data being transmitted. For example, where the channel is known to have long periods of infidelity, a burst error code might be best suited for that application. Where only short, infrequent errors are expected, a simple parity code might be best. It should be understood that, unless otherwise apparent or indicated, problems and solutions that are applicable to errors might also apply to erasures and vice versa. For example, an error that is a known error can be discarded and then treated identically as an erasure.
The term “communication” is used in a broad sense, and includes, but is not limited to, transmission of digital data of any form through space and/or time.
Data transmission is straightforward when a transmitter and a receiver have all of the computing power and electrical power needed for communications, and the channel between the transmitter and receiver is reliable enough to allow for relatively error-free communications. Data transmission becomes more difficult when the channel is in an adverse environment, or the transmitter and/or receiver has limited capability. In certain applications, uninterrupted error-free communication is required over long periods of time. For example, in digital television systems it is expected that transmissions will be received error-free for periods of many hours at a time. In these cases the problem of data transmission is difficult even in conditions of relatively low levels of errors.
Another scenario in which data communication is difficult is where a single transmission is directed to multiple receivers that may experience widely different conditions in terms of data loss. The conditions experienced by a given receiver may vary widely or may be relatively constant over time.
One solution is the use of forward error correcting (FEC) techniques, wherein data is coded at the transmitter in such a way that a receiver can correct transmission erasures and errors. Where feasible, a reverse channel from the receiver to the transmitter allows for the receiver to relay information about these errors to the transmitter, which can then adjust its transmission process accordingly. Often, however, a reverse channel is not available or feasible, or is available only with limited capacity. For example, in cases in which the transmitter is transmitting to a large number of receivers, the transmitter might not be able to maintain reverse channels from all the receivers. In another example, the communication channel may be storage medium. Thus data is transmitted chronologically forward through time, and unless someone invents a time travel machine that can go back in time, a reverse channel for this medium is impossible. As a result, communication protocols often need to be designed without a reverse channel or with a limited capacity reverse channel and, as such, the transmitter may have to deal with widely varying channel conditions without prior knowledge of those channel conditions.
In the case of a packet protocol used for data transport over a channel that can lose packets, a file, stream, or other block of data to be transmitted over a packet network is partitioned into equally-sized input symbols. Encoding symbols the same size as the input symbols are generated from the input symbols using an FEC code, and the encoding symbols are placed and sent in packets. The “size” of a symbol can be measured in bits, whether or not the symbol is broken into a bit stream, where a symbol has a size of M bits when the symbol is selected from an alphabet of 2M symbols. In such a packet-based communication system, a packet oriented erasure FEC coding scheme might be suitable.
A file transmission is called reliable if it allows the intended recipient to recover an exact copy of the original file despite erasures in the network. A stream transmission is called reliable if it allows the intended recipient to recover an exact copy of each part of the stream in a timely manner despite erasures in the network. Both file transmission and stream transmission can instead be not entirely reliable, but somewhat reliable, in the sense that some parts of the file or stream are not recoverable or, for streaming, some parts of the stream might be recoverable but not in a timely fashion.
Protection against erasures during transport has been the subject of much study with the object of achieving reliable or somewhat reliable communication over a communication channel or network which does not itself guarantee reliable delivery of data.
Encoding and decoding of forward error correction codes designed to protect against erasures generally can generally be achieved by performing an appropriate sequence of operations amongst symbols. Many operations are known in the art which may be combined in appropriate sequences in order to obtain forward error correction codes with different properties. These operations include, but are not restricted to, simple bitwise exclusive OR (XOR) operations and operations that can be obtained from the operation of elements of a finite field upon symbols. Such operations are well-known in the art and are described in detail for example in “Shokrollahi III”. Other operations may be obtained by combination of simpler operations. Such operations are referred to herein as “symbol operations”.
The bitwise exclusive OR operation is denoted herein by ⊕, that is, given two symbols A and B we denote the bitwise XOR of A and B as A⊕B. A sequence of such operations is denoted herein by the symbol Σ, that is given a sequence of symbols A0, A1, . . . An then the bitwise XOR of these symbols is denoted herein both by A0⊕A1⊕ . . . ⊕An and by the notation “ΣAi for i=0, . . . , n”. The operation of a finite field element upon a symbol is denoted herein by the symbol *, that is, given a finite field element β and a symbol C, the operation of β upon the symbol C is denoted herein by β*C.
Examples of such codes, based on symbol operations, include simple parity codes, Reed-Solomon codes, LDGM Staircase and LDGM Triangle codes and chain reaction codes (also commonly referred to as “fountain codes”) such as those described in “Luby I,” “Shokrollahi I” and “Shokrollahi III.”
We will use the terms “input symbols” and “output symbols” to refer to collections of symbols before and after (respectively) some sequence of symbol operations has been performed. In general, forward error correction codes are constructed from a sequence of symbol operations which transforms a collection of input symbols into a (usually larger) collection of output symbols. Such a transformation may be used as the encoding operation of a forward error correction code. A process generally exists whereby a suitable subset of the output symbols may be transformed into the input symbols by means of a further sequence of symbol operations. Such a transformation may be used as the decoding operation of a forward error correction code. In some cases, the set of output symbols includes exact copies of the input symbols, in which case the code is known as “systematic”. Systematic codes have several advantages that are well known to those of skill in the art of forward error correction. Non-systematic codes may in many cases be transformed into systematic codes, for example as disclosed in “Shokrollahi IV”. For example, this is possible in the case that a subset of the output symbols of size equal to the set of input symbols can be identified which is suitable for performing a decoding operation. A decoding operation may thus be performed on such a set of output symbols whose values are set to the original symbols to be communicated. This operation will result in a set of input symbols which can then be mapped to a larger set of output symbols using the original transformation. The resulting larger set of output symbols will necessarily include the original symbols and thus the code is systematic.
Properties of forward error correction codes which may be of interest and which may be influenced by the choice of and sequence of symbol operations include the error correction capability of the code and the computational complexity of the code. Error correction capability is generally a determined by the construction of the code, which is often described in terms of a specific exemplary encoding algorithm or in terms of mathematical relationships between the input and output symbols of the code.
Computational complexity is a property of both the construction of the code and of a specific implementation of a code. Computational complexity might be measured by the number of atomic operations required per symbol (or per other units) in encoding and/or decoding. For example, an encoder that performs five additions per symbol encoded is less “complex” than an encoder that performs ten additions per symbol encoded. Computational complexity determinations can take into account the type of atomic operation (five multiplications might be more complex than five additions) and average complexity (doing three adds half the time and seven adds the other half of the time might be considered of equal complexity with five adds). It should be noted that a specific implementation may employ algorithms which are different from the exemplary encoding algorithm through which the code is defined yet which still result in identical outputs when provided with the same inputs as the exemplary algorithm. Many algorithms may exist which implement the same forward error correction code.
It is desirable to have an encoding/decoding process and/or an encoder/decoder that uses low computational complexity and has low memory requirements.